#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0007.py
@time: 2021/9/9 13:57
@desc:
'''
# blank 返回长度为 n 的由空格组成的字符串
def blank(n: int) -> str:
    return ' ' * n

class Solution:
    def fullJustify(self, words: list, maxWidth: int) -> list:
        ans = []
        right, n = 0, len(words)
        while True:
            left = right  # 当前行的第一个单词在 words 的位置
            sumLen = 0  # 统计这一行单词长度之和
            # 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格, len(word[right])——当前单词长度, right - left 空格数量
            # 判断 单词 + 空格 是否会超过最大值， 会的话就不取新词，而将剩下没有满的，按照空格补上
            while right < n and sumLen + len(words[right]) + right - left <= maxWidth:
                sumLen += len(words[right]) # 单词数量自增
                right += 1

            # 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            if right == n:
                s = " ".join(words[left:])
                ans.append(s + blank(maxWidth - len(s)))
                break

            numWords = right - left
            numSpaces = maxWidth - sumLen # 剩下需要补齐的空格

            # 当前行只有一个单词：该单词左对齐，在行末填充空格
            if numWords == 1:
                ans.append(words[left] + blank(numSpaces))
                continue

            # 当前行不只一个单词
            avgSpaces = numSpaces // (numWords - 1) # 计算当前行每个单词之间平均需要补的空格
            extraSpaces = numSpaces % (numWords - 1) # 计算无法整除时多出来的空格
            s1 = blank(avgSpaces + 1).join(words[left:left + extraSpaces + 1])  # 拼接额外加一个空格的单词, join函数可以将字符插在列表中每个元素之间, 所以需要在[left, left + extraSpaces +1]之间的每个词都加多一个空格
            s2 = blank(avgSpaces).join(words[left + extraSpaces + 1:right])  # 拼接其余单词
            ans.append(s1 + blank(avgSpaces) + s2)

        return ans

class Solution02:
    def blank(self, n: int):
        return ' '*n
    def fullJustify(self, words: list, maxWidth: int) -> list:
        ans = []
        right, n = 0, len(words) # left, right 游标指出纳入到哪个单词, n记录单词长度

        while True:
            left = right # 当前行的第一个单词的在nums的位置
            sumLen = 0 # 当前行的长度

            while right < n and sumLen + len(words[right]) + right - left <=  maxWidth:
                sumLen += len(words[right])
                right += 1

            # 当选出足够的 maxWidth 后
            # 计算纳入的多少个单词
            numWord = right - left

            # 计算出 多出的空格
            numSpace = maxWidth - sumLen

            # 特殊情况
            # 1. 只有一个单词
            if numWord == 1:
                s = words[left] + self.blank(numSpace)
                ans.append(s)
                continue

            # 2. 最后一行: 应为左对齐，而不是左右两端对齐
            if right == n:
                s = ' '.join(words[left:])
                ans.append(s + self.blank(maxWidth - len(s)))
                break

            # 计算出 每个单词之间所需的空格
            averSpace = numSpace // (numWord - 1)

            # 计算出是否有多出的空格(即整除的余数)
            extraSpace = numSpace % (numWord - 1)

            # 多出extraSpace个空格，就要平均分配到前extraSpace，使得他们每个要(averSpace + 1)个空格
            s1 = (self.blank(averSpace + 1)).join(words[left: left + 1 +extraSpace])
            s2 = self.blank(averSpace).join(words[left + 1 +extraSpace: right])

            s = s1 + self.blank(averSpace) + s2
            ans.append(s)

        return ans

if __name__ == '__main__':
    s = Solution()
    words = ["This", "is", "an", "example", "of", "text", "justification."]
    maxWidth = 16
    a = s.fullJustify(words, maxWidth)
    print(a)